import lib.problem as problem
import unittest

numbers1 =[
                           75,
                         95, 64,
                       17, 47, 82,
                     18, 35, 87, 10,
                   20, 04, 82, 47, 65,
                 19, 01, 23, 75, 03, 34,
               88, 02, 77, 73, 07, 63, 67,
             99, 65, 04, 28, 06, 16, 70, 92,
           41, 41, 26, 56, 83, 40, 80, 70, 33,
         41, 48, 72, 33, 47, 32, 37, 16, 94, 29,
       53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,
     70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,
   91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,
 63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,
4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23
]


numbers2 = [
		   3,
		  7, 4,
		 2, 4, 6,
		8, 5, 9, 3
		]


class Problem018(problem.Problem):
	def __init__(self):
		problem.Problem.__init__(self, 18)
		self.numbers = numbers1
		
	def getRowNumber(self, n):
		row = 1
		lastInRow = 0
		
		while lastInRow < n:
			row += 1
			lastInRow += row
			
		return row
	
		
	def getNextPositions(self, pos):
		rowNumber = self.getRowNumber(pos)
		left = pos + rowNumber
		right = left + 1
		return (left, right)
	
	
	def recursiveCalc(self, pos, sumSoFar):
		if pos >= len(self.numbers):
			return 0
		
		(left, right) = self.getNextPositions(pos)
		
		leftSum  = self.recursiveCalc(left, sumSoFar)
		rightSum = self.recursiveCalc(right, sumSoFar)
		
		sum = leftSum
		if rightSum > leftSum:
			sum = rightSum
			
		sum += self.numbers[pos] 
		
		return sum
	
	def solve(self):
		return self.recursiveCalc(0, 0)
	
	
class Problem018Tester(unittest.TestCase):
	
	def setUp(self):
		self.p018 = Problem018()
		
	def testGetRowNumber0(self):
		row = self.p018.getRowNumber(0)
		self.assertEquals(1, row)
		
	def testGetRowNumber7(self):
		row = self.p018.getRowNumber(7)
		self.assertEquals(4, row)
		
	def testGetRowNumber21(self):
		row = self.p018.getRowNumber(21)
		self.assertEquals(7, row)
		
	def testGetNexyPositions0(self):
		nextPos = self.p018.getNextPositions(0)
		self.assertEquals((1, 2), nextPos)
		
	def testGetNexyPositions9(self):
		nextPos = self.p018.getNextPositions(9)
		self.assertEquals((13, 14), nextPos)
		
	def testGetNexyPositions10(self):
		nextPos = self.p018.getNextPositions(10)
		self.assertEquals((15, 16), nextPos)
	
	def testSolveNumbers2(self):
		self.p018.numbers = numbers2
		self.assertEquals(23, self.p018.solve())
		
	def testSolve(self):
		self.assertEquals(1074, self.p018.solve())
